package com.atguigu.linklist;

public class FindTheEntranceOfTwoRingList {
    public static ListNode haveRing(ListNode head){
        if(head==null) return null;
        if(head.next==null) return head;
        ListNode fast=head.next.next;
        ListNode slow=head.next;
        while(fast!=slow && fast!=null){
            fast=fast.next.next;
            slow=slow.next;
        }
        if(fast==null){
            return null; //无环
        }
        fast=head;
        while(fast!=slow){
            fast=fast.next;
            slow=slow.next;
        }
        return fast; //环的入口节点
    }
    //找到两个带环链表的相交节点
    public static ListNode findTheEntranceOfRing(ListNode head1,ListNode head2){
        ListNode loop1=haveRing(head1);
        ListNode loop2=haveRing(head2);
        if(loop1!=null && loop2!=null){
            if(loop1==loop2){ //情况二
                 //以类似普通的无环相交链表求解
                //return
            }else{
                ListNode cur=loop1.next;
                while(cur!=loop1){
                    if(cur==loop2){
                        //情况三，返回loop1或loop2
                        return loop1;
                    }
                    cur=cur.next;
                }
                return null; //情况一，无相交
            }
        }
        return null;
    }
}
